import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Test {

    public static void main(String[] args) {
        String s = "aaaaaaa";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("aaaa");
        wordDict.add("aaa");
        wordBreak(s,wordDict);

    }
    public static boolean wordBreak(String s, List<String> wordDict) {

        boolean[] dp = new boolean[s.length()+1];// 前i个字符能否匹配成功
        dp[0] = true;

        for(int end = 1; end <= s.length(); end++){
            for(int start = 0; start < end; start++){
                String str = s.substring(start,end);
                if (wordDict.contains(str) && dp[start]) {
                    dp[end] = true;
                }
            }
        }
        return dp[s.length()];
    }

    public static void main6(String[] args) {
        int[] coins = {2};
        coinChange(coins,3);
    }
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;

        for(int i = 0; i < coins.length; i++){
            for(int j = coins[i]; j <= amount; j++){
                dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }


    public static void main5(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int num = in.nextInt();
            while(num >= 10){
                num = numRoot(num);
            }
            System.out.println(num);
        }
    }
    public static int numRoot(int num){
        int ret = 0;
        while(num > 0){
            ret += num % 10;
            num /= 10;
        }
        return ret;
    }


    public static void main4(String[] args) {
        Thread t = new Thread(){
            @Override
            public void run() {
                System.out.println("dianping");
            }
        };
        t.run();
        System.out.println("dazhong");


    }
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] nums = new int[strs.length][2];
        // nums[0] 表示该字符串有几个 0
        // nums[1] 表示该字符串有几个 1
        for(int i = 0; i < strs.length; i++){
            int zero = 0;
            int one = 0;
            for(char c : strs[i].toCharArray()){
                if(c == '0') zero++;
                else one++;
            }
            nums[i] = new int[]{zero,one};
        }

        int[][] dp = new int[m+1][n+1];// m个0  n个1

        // 字符串层 ---- 物品层
        for(int i = 0; i < nums.length; i++){
            // m层 ---- 0的个数
            for(int j = m; j >= nums[i][0]; j--){
                // n层 ---- 1的个数
                for(int k = n; k >= nums[i][1]; k--){
                    // 不拿当前字符串  -----  dp[i][j]
                    // 拿当前字符 ----- dp[j-nums[i][0]][k-nums[i][1]] + 1
                    dp[j][k] = Math.max(dp[j][k],dp[j-nums[i][0]][k-nums[i][1]] + 1);
                }
            }
        }

        return dp[m][n];
    }

    public static void main3(String[] args) {
        System.out.println(myAtoi("-91283472332"));
    }
    public static int myAtoi(String s) {
        char[] chars = s.toCharArray();
        int index = 0;
        while (index < chars.length && chars[index] == ' ') index++;
        if (index == chars.length) return 0;
        boolean sign = false;// 为正数
        if (chars[index] == '+') {
            index++;
        }else if (chars[index] == '-') {
            sign = true;
            index++;
        }

        int ret = 0;
        for (int i = index; i < chars.length; i++) {
            if (chars[i] >= '0' && chars[i] <= '9'){
                int num = chars[i] - '0';
                if (sign && -ret < (Integer.MIN_VALUE+num) / 10) return Integer.MIN_VALUE;
                if (!sign && ret > (Integer.MAX_VALUE-num) / 10)  return Integer.MAX_VALUE;
                ret = ret*10 + num;
            }else{
                break;
            }
        }
        // 为负数
        if (sign) return -ret;
        return ret;
    }


    public static void main2(String[] args) {
        int[] stones = {1,2};
        System.out.println(lastStoneWeightII(stones));

        System.out.println(Integer.MAX_VALUE);
    }
    public static int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i = 0; i < stones.length; i++){
            sum += stones[i];
        }
        int target = sum / 2;
        int[][] dp = new int[stones.length][target+1];
        // 初始化
        for(int i = stones[0]; i <= target; i++){
            dp[0][i] = stones[0];
        }

        for(int i = 1; i < stones.length; i++){
            for(int j = 1; j <= target; j++){
                if(j >= stones[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        int left = sum - dp[stones.length-1][target];
        return left - dp[stones.length-1][target];
    }




    static List<int[]> list = new ArrayList<>();// 用来记录路径的list
    static List<int[]> ret;// 最终路径
    static int endR;
    static int endL;

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int rows = scanner.nextInt();
        int lines = scanner.nextInt();
        endR = rows;
        endL = lines;
        int[][] maze = new int[rows][lines];

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < lines; j++){
                maze[i][j] = scanner.nextInt();
            }
        }
        boolean[][] path = new boolean[rows][lines];
        path[0][0] = true;
        back(0,0,maze,path);
        for(int i = 0; i < ret.size(); i++){
            int[] step = ret.get(i);
            System.out.println(step[0] + " " + step[1]);
        }
    }
    // 回溯
    public static void back(int row,int line,int[][] maze,boolean[][] path){
        list.add(new int[]{row,line});

        if(row == endR - 1 && line == endL - 1){
            ret = new ArrayList<>(list);
            return;
        }

        // 下
        if(row < endR - 1 && maze[row+1][line] == 0){
            if(!path[row+1][line]){
                path[row+1][line] = true;
                back(row+1,line,maze,path);
                path[row+1][line] = false;
                list.remove(list.size()-1);
            }
        }
        // 右
        if(line < endL - 1 && maze[row][line+1] == 0){
            if(!path[row][line+1]){
                path[row][line+1] = true;
                back(row,line+1,maze,path);
                path[row][line+1] = false;
                list.remove(list.size()-1);
            }
        }
        // 上
        if(row > 0 && maze[row-1][line] == 0){
            if(!path[row-1][line]){
                path[row-1][line] = true;
                back(row-1,line,maze,path);
                path[row-1][line] = false;
                list.remove(list.size()-1);
            }
        }
        // 左
        if(line > 0 && maze[row][line-1] == 0){
            if(!path[row][line-1]){
                path[row][line-1] = true;
                back(row,line-1,maze,path);
                path[row][line-1] = false;
                list.remove(list.size()-1);
            }
        }

    }
}
